#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#define MAXSIZE 30

typedef int Data;

typedef struct Node {
  struct Node *next;
  Data data;
  int index;
} Looplink, *Head;

void empty(void);

Head initLink(void);

void showLink(const Head head);

void findAndOut(Head head, int *m);

int main(void) {
  int m;
  Head head = initLink();
  showLink(head);
  printf("请输入m=");
  scanf("%d", &m);
  empty();
  while (head != head->next) {
    findAndOut(head, &m);
  }
  puts("");
  return false;
}

void empty(void) {
  while (getchar() != '\n') {
    continue;
  }
}

Head initLink(void) {
  Head head;
  Looplink *node, *end;
  Data data;
  int index;
  int number = 31;
  head = (Head)malloc(sizeof(Looplink));
  end = head;
  puts("初始化约瑟夫环人数");
  while (number > MAXSIZE) {
    printf("请确保人数小于%d\n", MAXSIZE);
    printf("请输入初始化人数:");
    scanf("%d", &number);
    empty();
  }
  puts("输入每个人拥有的密码");
  for (index = 0; index < number; index++) {
    node = (Looplink *)malloc(sizeof(Looplink));
    scanf("%d", &data);
    node->data = data;
    node->index = index + 1;
    end->next = node;
    end = node;
  }
  empty();
  end->next = head;
  return head;
}

void showLink(const Head head) {
  Looplink *node;
  node = head->next;
  puts("当前密码为:");
  while (node != head) {
    printf("%2d\t", node->data);
    node = node->next;
  }
  puts("");
}

void findAndOut(Head head, int *m) {
  Looplink *previous, *node, *end;
  int i;
  previous = head;
  end = head;
  while (end->next != head) {
    end = end->next;
  }
  for (i = 1; i < *m; i++) {
    previous = previous->next;
    if (previous->next == head) {
      previous = head;
    }
  }
  node = previous->next;
  if (previous != head) {
    end->next = head->next;
    previous->next = head;
  }
  head->next = node->next;
  printf("%2d\t", node->index);
  m = &node->data;
  free(node);
}
